package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-18 11:20
 * @Description: NumDecodings$91-解码方法-https://leetcode-cn.com/problems/decode-ways/
 */
public class NumDecodings {

	/**
	 * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
	 *
	 * 'A' -> 1
	 * 'B' -> 2
	 * ...
	 * 'Z' -> 26
	 * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
	 *
	 * 题目数据保证答案肯定是一个 32 位的整数。
	 *
	 *
	 * 示例 1：
	 *
	 * 输入：s = "12"
	 * 输出：2
	 * 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
	 * 示例 2：
	 *
	 * 输入：s = "226"
	 * 输出：3
	 * 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
	 * 示例 3：
	 *
	 * 输入：s = "0"
	 * 输出：0
	 *
	 * 示例 4：
	 *
	 * 输入：s = "1"
	 * 输出：1
	 * 示例 5：
	 *
	 * 输入：s = "2"
	 * 输出：1
	 *
	 * 提示：
	 *
	 * 1 <= s.length <= 100
	 * s 只包含数字，并且可能包含前导零。
	 *
	 * 【解析】
	 * step1:确定状态
	 * 		 	解密数字串即“划分”若干段数字，每段数字对应一个字母
	 * 	1.最后一步（最后一段）：对应一个字母
	 * 	- A,B,...或Z
	 * 	- 这个字母加密时变成1,2，...,或26，
	 * 	如：
	 * 		0	1	2		N-4	N-3	N-2	N-1
	 * 		8	2	3 ...	1	3	1	2
	 * 		最后一个字母，要么是2即B，要么是12即L
	 * 		1.最后字母是B,假设前面有100种
	 * 		2.最后字母是L,假设前面有50中，
	 * 		所以总共有100+50种
	 * 	2.子问题：
	 *     	-设数字串长度为N
	 *     	-要求数字串前N个字符串的解密方式数
	 *     	-需要知道数字串前N-1和数字串N-2个字符的解密方式数
	 * 	故，状态：设数字串S前i个数字解密成字符串有f[i]种方式
	 * step2:转移方程：
	 *     	-设数字串S的前i个数字解密成字符串有f[i]种方式
	 *     	f[i] = f[i-1]S[i-1]对应一个字母+f[i-2]S[i-2]S[i-1]对应一个字母
	 *     字符串S前i个数字解密成字母串方式数	  数字串s前i-1个数字解密成字母串方式数 数字串s前i-2个数字解密成字符串方式数
	 *
	 * 	这里提到的“前i个”，同划分型相似，只要不是坐标型，都是
	 *
	 * step3:初始条件和边界情况
	 * 	-设数字串S前i个数字解密成字母串有f[i]种方式
	 * 	-初始条件：f[0],即串有1种方式解密，解密成空串
	 *
	 * 	假如使用坐标：
	 * 		f[i]:S[0]...S[i]的解密方式，此时f[0]对应的不是空串，而是数字串的第一个元素S[0],此时就要进行对应的判断：、
	 * 		- S[0]=[1~9],f[0]=...
	 * 		- S[0]=0,f[0]=...
	 * 		处理起来麻烦，使用前i个解决，类似需序列化型动态规划
	 * 	-边界情况：如果i=1,只看最后一个数字
	 *
	 * step4:计算顺序
	 * 	- f[0],f[1],...f[N]
	 * 	- 最后结果是f[N]
	 * 	- 时间复杂度O(N),空间复杂度O(N)
	 *
	 *
	 *
	 */

	public int numDecodings(String s) {

		char[] chars = s.toCharArray();

		int n = chars.length;
		if(n == 0){
			return 0;
		}

		// 动态规划，存储结果
		// 0 ~ n,长度n+1
		int[] f = new int[n+1];

		// init 前0个，解密只有一种空串
		f[0] = 1;

		// 划分型，按照前多少个进行处理
		for (int i = 1; i <= n; i++) {
			f[i] = 0;
			// 第一种，最后一位做字母，累加，最后一个构成字母
			int t = chars[i-1]-'0';
			if(t>=1 && t<=9){
				f[i] += f[i-1];
			}
			// 第二种，最后两位做字母，累加,至少两个数字
			if(i >= 2){
				// 最后两个组成字母
				t = (chars[i-2]-'0')*10+chars[i-1]-'0';
				if(10<=t && t<=26){
					f[i] += f[i-2];
				}
			}
		}

		return f[n];
	}
	public static void main(String[] args) {
		String str = "12";
		NumDecodings instance = new NumDecodings();
		System.out.println(instance.numDecodings(str));
	}
}
